package com.evil.kingdom.utils;

import com.evil.common.core.exception.BusinessException;
import com.evil.kingdom.pojo.entity.action.AbstractPosition;
import com.evil.kingdom.pojo.entity.action.ActionPosition;
import com.evil.kingdom.pojo.entity.action.BattleLayout;
import com.evil.kingdom.pojo.entity.action.RoutePosition;
import com.evil.kingdom.pojo.enums.result.RCodeEnum;
import jakarta.validation.constraints.Min;
import jakarta.validation.constraints.NotNull;

import java.util.*;
import java.util.function.BiConsumer;

/**
 * Dijkstra算法
 *
 * @author liyang
 * @date 2024-05-24 23:17
 */
public class DijkstraUtil {

    /**
     * 计算多个线段距离（带权比）
     *
     * @param actionPositions actionPositions
     * @return 权
     */
    public static double calWeight(Collection<ActionPosition> actionPositions) {
        return actionPositions.stream().mapToDouble(DijkstraUtil::calWeight).sum();
    }

    /**
     * 计算两点之间距离（带权比）
     *
     * @param actionPosition actionPosition
     * @return 权
     */
    public static double calWeight(ActionPosition actionPosition) {
        return DijkstraUtil.calWeight(actionPosition.getDepart(), actionPosition.getDest(), actionPosition.getSpeed());
    }

    /**
     * 计算两点之间距离（带权比）
     *
     * @param depart 出发点
     * @param dest   目的点
     * @param speed  速度
     * @return 距离
     */
    public static double calWeight(AbstractPosition depart, AbstractPosition dest, Double speed) {
        double dx = dest.getX() - depart.getX();
        double dy = dest.getY() - depart.getY();
        return DijkstraUtil.calWeight(dx, dy) * speed;
    }

    /**
     * 计算两点之间距离
     *
     * @param slope slope
     * @return 距离
     */
    public static double calWeight(Slope slope) {
        return DijkstraUtil.calWeight(slope.dx, slope.dy);
    }

    /**
     * 计算两点之间距离
     *
     * @param dx dx
     * @param dy dy
     * @return 距离
     */
    public static double calWeight(double dx, double dy) {
        return Math.sqrt(dx * dx + dy * dy);
    }

    /**
     * 计算步进
     *
     * @param depart 出发点
     * @param dest   目的点
     * @param step   步进长度
     * @return 结果点
     */
    public static AbstractPosition offset(AbstractPosition depart, AbstractPosition dest, double step) {
        // 求斜率
        Slope sloped = DijkstraUtil.calSlope(depart, dest);
        return DijkstraUtil.offset(depart, dest, sloped, step);
    }

    /**
     * 计算步进
     *
     * @param depart 出发点
     * @param dest   目的点
     * @param sloped 斜率
     * @param step   步进长度
     * @return 结果点
     */
    public static AbstractPosition offset(AbstractPosition depart, AbstractPosition dest, Slope sloped, double step) {
        if (0 == sloped.slope) {
            throw new BusinessException(RCodeEnum.RUN_ERROR);
        }
        // x轴相同，则y轴直接相加
        if (Double.MAX_VALUE == sloped.slope) {
            // 不可以超过终点
            double y = sloped.gtDY() ? Math.min((depart.getY() + step), dest.getY()) : Math.max((depart.getY() - step), dest.getY());
            return new AbstractPosition(depart.getX(), y);
        }
        // y轴相同，则x轴直接相加
        if (Double.MIN_VALUE == sloped.slope) {
            // 不可以超过终点
            double x = sloped.gtDX() ? Math.min((depart.getX() + step), dest.getX()) : Math.max((depart.getX() - step), dest.getX());
            return new AbstractPosition(x, depart.getY());
        }
        double atan = Math.atan(sloped.slope);
        // 计算deltaX和deltaY
        double deltaX = step * Math.cos(atan);
        double deltaY = step * Math.sin(atan);

        double dx = sloped.gtDX() ? (depart.getX() + deltaX) : (depart.getX() - deltaX);
        double dy = sloped.gtDX() ? (depart.getY() + deltaY) : (depart.getY() - deltaY);
        return new AbstractPosition(dx, dy);
    }

    /**
     * 自动计算步进
     *
     * @param depart  出发点
     * @param dest    目的点
     * @param step    步进长度
     * @param unit    移动单位
     * @param minUnit 最小移动单位
     * @param layout  布局
     * @return 结果点
     */
    public static AbstractPosition offsetAI(@NotNull(message = "depart not null") final AbstractPosition depart,
                                            @NotNull(message = "dest not null") final AbstractPosition dest,
                                            @Min(value = 0, message = "step gt 0") final double step,
                                            @Min(value = 0, message = "unit gt 0") final double unit,
                                            @Min(value = 0, message = "minUnit gt 0") final double minUnit,
                                            @NotNull(message = "layout not null") final BattleLayout layout) {
        AbstractPosition newP = null;
        for (double i = minUnit; i <= step; i += minUnit) {
            newP = DijkstraUtil.offset(depart, dest, i);

            final AbstractPosition rd = new AbstractPosition(dest);
            double minOffset = 0;
            boolean sign = false;
            while (layout.nearest(newP, unit, depart, dest)) {
                minOffset += minUnit;
                sign = !sign;
                if (!rd.offset(sign ? 0 + minOffset : 0 - minOffset)) {
                    break;
                }
                newP = DijkstraUtil.offset(depart, rd, i);
            }
        }
        return newP;
    }

    /**
     * 平移计算步进
     *
     * @param depart 出发点
     * @param sloped 斜率
     * @param step   步进长度
     * @return 结果点
     */
    public static AbstractPosition offsetParallel(@NotNull(message = "depart not null") final AbstractPosition depart,
                                                  @NotNull(message = "sloped not null") Slope sloped,
                                                  @Min(value = 0, message = "step gt 0") final double step) {
        double absX = Math.abs(sloped.dx);
        double absY = Math.abs(sloped.dy);
        // 判断是否需要移动
        if (absX > step || absY > step) {
            AbstractPosition result = new AbstractPosition();
            if (sloped.dx > sloped.dy) {
                // 优先移动x轴
                result.setX(sloped.dx > 0 ? (depart.getX() - step) : (depart.getX() + step));
            } else {
                // 优先移动y轴
                result.setY(sloped.dy > 0 ? (depart.getY() - step) : (depart.getY() + step));
            }
            return result;
        }
        return null;
    }

    /**
     * 计算两点斜率
     *
     * @param depart depart
     * @param dest   dest
     * @return 斜率（0-xy相同, max-x轴相同, min-y轴相同, 其他-斜率）
     */
    public static Slope calSlope(AbstractPosition depart, AbstractPosition dest) {
        // 求斜率
        double dx = dest.getX() - depart.getX();
        double dy = dest.getY() - depart.getY();
        double slope;
        if (0 != dx && 0 != dy) {
            slope = dy / dx;
        } else if (0 == dx && 0 == dy) {
            slope = 0d;
        } else if (0 == dy) {
            slope = Double.MIN_VALUE;
        } else {
            slope = Double.MAX_VALUE;
        }
        return new Slope(dx, dy, slope);
    }

    /**
     * 斜率
     *
     * @param dx    dx
     * @param dy    dy
     * @param slope slope
     */
    public record Slope(double dx, double dy, Double slope) {
        public boolean gtDX() {
            return dx > 0;
        }

        public boolean gtDY() {
            return dy > 0;
        }

        public boolean gtSlope() {
            return slope > 0;
        }

        public boolean sameSlope(Slope slope) {
            return (null == this.slope && null == slope.slope) || (null != this.slope && this.slope.equals(slope.slope));
        }
    }

    /**
     * Node类，用于优先队列中存储节点及其距离
     *
     * @param name          当前城池名称
     * @param from          从哪个城池过来的
     * @param distance      权重
     * @param routePosition 数据记录
     */
    private record Node(String name, DijkstraUtil.Node from, Double distance, RoutePosition routePosition) {

        public void collectName(List<String> result) {
            if (null != this.from) {
                this.from.collectName(result);
            }
            result.add(this.name);
        }

        public void collect(List<RoutePosition> result) {
            if (null != this.from) {
                this.from.collect(result);
                result.add(routePosition);
            }
        }
    }

    public static LinkedList<RoutePosition> shortestPath(Map<String, List<RoutePosition>> graph, String source, String target) {
        return DijkstraUtil.shortestPath(graph, source, target, new LinkedList<>(), Node::collect);
    }

    public static List<String> shortestPathName(Map<String, List<RoutePosition>> graph, String source, String target) {
        return DijkstraUtil.shortestPath(graph, source, target, new LinkedList<>(), Node::collectName);
    }

    private static <T> T shortestPath(Map<String, List<RoutePosition>> graph, String source, String target, T result, BiConsumer<Node, T> callback) {
        // 初始化距离数组，将所有节点的距离设为无穷大，除了源节点为0
        Map<String, Double> distances = new HashMap<>();
        for (String node : graph.keySet()) {
            distances.put(node, Double.MAX_VALUE);
        }
        distances.put(source, 0d);

        // 使用优先队列（最小堆）来存储待访问的节点
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingDouble(a -> a.distance));
        pq.add(new Node(source, null, 0d, null)); // 初始时将源节点加入队列

        // 标记数组，记录节点是否已被访问
        Set<String> visited = new HashSet<>();

        while (!pq.isEmpty()) {
            Node currentNode = pq.poll(); // 取出当前距离最短的节点
            String currentNodeName = currentNode.name;
            double currentDistance = currentNode.distance;

            // 如果当前节点已经被访问过，跳过
            if (visited.contains(currentNodeName)) {
                continue;
            }

            visited.add(currentNodeName); // 标记当前节点为已访问

            // 如果当前节点是目标节点，返回当前距离
            if (currentNodeName.equals(target)) {
                callback.accept(currentNode, result);
                return result;
            }

            // 遍历当前节点的所有邻居
            for (RoutePosition routePosition : graph.get(currentNodeName)) {
                String neighbor = routePosition.getDestName();
                double weight = routePosition.getWeight();

                // 如果邻居节点尚未访问过，并且从源节点通过当前节点到邻居节点的距离更短
                if (!visited.contains(neighbor) && currentDistance + weight < distances.get(neighbor)) {
                    distances.put(neighbor, currentDistance + weight); // 更新距离
                    pq.add(new Node(neighbor, currentNode, currentDistance + weight, routePosition)); // 将邻居节点加入优先队列
                }
            }
        }

        // 如果找不到路径，返回-1或其他表示错误的值
        return result;
    }
}
